Search results for "Variable elimination"
showing 4 items of 4 documents
Efficient CNF Encoding of Boolean Cardinality Constraints
2003
In this paper, we address the encoding into CNF clauses of Boolean cardinality constraints that arise in many practical applications. The proposed encoding is efficient with respect to unit propagation, which is implemented in almost all complete CNF satisfiability solvers. We prove the practical efficiency of this encoding on some problems arising in discrete tomography that involve many cardinality constraints. This encoding is also used together with a trivial variable elimination in order to re-encode parity learning benchmarks so that a simple Davis and Putnam procedure can solve them.
A new branch-and-price algorithm for the traveling tournament problem
2010
Abstract The traveling tournament problem ( ttp ) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. For solving the problem exactly, we propose a new branch-and-price approach. The starting point is a new compact formulation for the ttp . The corresponding extensive formulation resulting from a Dantzig-Wolfe decomposition is identical to one given by Easton, K., Nemhauser, G., Trick, M., 2003. Solving the traveling tournament problem: a combined interger programming and constraint programming approach. In: Burke, E., De Causmaecker, P. (Eds.), Practice and Theory of Automated Timetabling IV, Volume 2740 of Lecture Notes i…
New cut-off criterion for uninformative variable elimination in multivariate calibration of near-infrared spectra for the determination of heroin in …
2008
A new cut-off criterion has been proposed for the selection of uninformative variables prior to chemometric partial least squares (PLS) modelling. After variable elimination, PLS regressions were made and assessed comparing the results with those obtained by PLS models based on the full spectral range. To assess the prediction capabilities, uninformative variable elimination (UVE)-PLS and PLS were applied to diffuse reflectance near-infrared spectra of heroin samples. The application of the proposed new cut-off criterion, based on the t-Students distribution, provided similar predictive capabilities of the PLS models than those obtained using the original criteria based on quantile value. H…
Probabilistic inference of approximations
2006
We consider probabilistic inductive inference of Godel numbers of total recursive functions when the set of possible errors is allowed to be infinite, but with bounded density. We have obtained hierarchies of classes of functions identifiable with different probabilities up to sets with fixed density. The obtained hierarchies turn out to be different from those which we have in the case of exact identification.